//////////////////////////////////////
// Fast Container Library           //
// MIT License - Copyright (c) 2012 //
//////////////////////////////////////

#pragma once

#include "vector_base.h"
#include "iterator.h"

FC_NAMESPACE_BEGIN


template <class T, class Allocator>
class vector : public vector_base<T, Allocator>
{
public:
	typedef size_t									size_type;
	typedef T										value_type;
	typedef T*										pointer;
	typedef const T*								const_pointer;
	typedef T&										reference;
	typedef const T&								const_reference;
	typedef T*										iterator;
	typedef const T*								const_iterator;
	typedef fc::reverse_iterator<iterator>			reverse_iterator;
	typedef fc::reverse_iterator<const_iterator>	const_reverse_iterator;
	typedef ptrdiff_t								difference_type;
	typedef vector<T, Allocator>					this_type;
	typedef vector_base<T, Allocator>				base_type;
	typedef typename base_type::allocator_type		allocator_type;

	using base_type::allocate;
	using base_type::deallocate;
	using base_type::allocate_copy;
	using base_type::allocate_fill;
	using base_type::m_begin;
	using base_type::m_end;
	using base_type::m_capacity;

	vector()
		: base_type()
		{
		}

	explicit vector( const allocator_type& alloc )
		: base_type(alloc)
		{
		}

	explicit vector( size_t n, const T& value = T(), const allocator_type& alloc = allocator_type() )
		: base_type(alloc)
		{
			InitializeValues( n, value );
		}

	template <class InputIterator>
		vector( InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type() )
		: base_type(alloc)
		{
			InitializeDispatch( first, last,
				typename is_integral<InputIterator>::type() );
		}

	vector( const this_type& x )
		: base_type()
		{
			InitializeIterator( x.size(), x.begin(), x.end() );
		}

	bool empty() const		{ return m_end == m_begin; }
	bool full() const		{ return m_end == m_capacity; }
	size_t size() const		{ return size_t(m_end - m_begin); }
	size_t max_size() const	{ return size_t(-1) / sizeof(T); }
	size_t capacity() const	{ return size_t(m_capacity - m_begin); }
	size_t unused() const	{ return size_t(m_capacity - m_end); }

	reference operator [] ( size_t i ) { return *(m_begin + i); }
	const_reference operator [] ( size_t i ) const { return *(m_begin + i); }

	reference at( size_t i )
	{
		FC_ASSERT(i < size());
		return *(m_begin + i);
	}

	const_reference at( size_t i ) const
	{
		FC_ASSERT(i < size());
		return *(m_begin + i);
	}

	reference		front()			{ return *m_begin; }
	const_reference front() const	{ return *m_begin; }
	reference		back()			{ return *(m_end - 1); }
	const_reference back()	const	{ return *(m_end - 1); }

	iterator		begin()			{ return m_begin; }
	const_iterator	begin() const	{ return m_begin; }
	iterator		end()			{ return m_end; }
	const_iterator	end() const		{ return m_end; }
	const_iterator	cbegin() const	{ return m_begin; }
	const_iterator	cend() const	{ return m_end; }
	reverse_iterator		rbegin()		{ return reverse_iterator(m_end); }
	const_reverse_iterator	rbegin() const	{ return const_reverse_iterator(m_end); }
	reverse_iterator		rend()			{ return reverse_iterator(m_begin); }
	const_reverse_iterator	rend() const	{ return const_reverse_iterator(m_begin); }

	pointer data()				{ return m_begin; }
	const_pointer data() const	{ return m_begin; }

	void reserve( size_t n )
	{
		if( n > capacity() )
			set_capacity(n);
	}

	void resize( size_t n, const T& value = T() )
	{
		// always respect the capacity request by the user.
		reserve(n);

		size_t currentSize = size();
		if( n > currentSize )
			insert_n( m_end, n - currentSize, value );
		else if( n < currentSize )
			erase( m_begin + n, m_end );
	}

	void reset() { m_end = m_begin; }
	void clear()
	{
		fc::destroy_range(m_begin, m_end);
		m_end = m_begin;
	}

	void shrink_to_fit() { set_capacity( size_t(m_end - m_begin) ); }
	void set_capacity( size_t newCapacity )
	{
		// only reallocate if capacity is being changed
		if( newCapacity != size_t(m_capacity - m_begin) )
		{
			const size_t newSize = size_t(m_end - m_begin);
			if( newCapacity < newSize )
				erase(m_begin + newCapacity, m_end);

			T* newBegin = newCapacity ? allocate_copy(newCapacity, m_begin, m_end) : 0;
			fc::destroy_range(m_begin, m_end);
			deallocate();

			m_begin = newBegin;
			m_end = newBegin + newSize;
			m_capacity = newBegin + newCapacity;
		}
	}
/*
	void SetCapacity( size_t newCapacity, true_type )
	{
		const size_t newSize = size_t(m_end - m_begin);
		if( newCapacity < newSize )
			m_end = newCapacity;

		T* newBegin = newCapacity ? allocate_copy(newCapacity, m_begin, m_end) : 0;
		deallocate();

		m_begin = newBegin;
		m_end = newBegin + newSize;
		m_capacity = newBegin + newCapacity;
	}
*/
	void assign( size_t n, const T& value ) { assign_n( n, value ); }
	void assign_n( size_t n, const T& value )
	{
		AssignValues( n, value, typename is_pod<T>::type() );
	}

	template <class InputIterator>
	void assign( InputIterator first, InputIterator last )
	{
		AssignDispatch( first, last,
			typename is_integral<InputIterator>::type() );
	}

	template <class ForwardIterator>
	void assign_iter( ForwardIterator first, ForwardIterator last )
	{
		AssignIterator( first, last, typename is_pod<T>::type() );
	}

	void insert_at( size_t pos, const T& value ) { insert( m_begin + pos, value ); }
	void insert_at( size_t pos, size_t n, const T& value ) { insert_n( m_begin + pos, n, value ); }

	iterator insert( iterator pos, const T& value )
	{
		return InsertValue( pos, value, typename is_pod<T>::type() );
	}

	inline void insert( iterator pos, size_t n, const T& value )
	{
		InsertValues( pos, n, value, typename is_pod<T>::type() );
	}

	inline void insert_n( iterator pos, size_t n, const T& value )
	{
		InsertValues( pos, n, value, typename is_pod<T>::type() );
	}

	template <class InputIterator> inline
	void insert( iterator pos, InputIterator first, InputIterator last )
	{
		InsertDispatch( pos, first, last,
			typename is_integral<InputIterator>::type() );
	}

	template <class InputIterator> inline
	void insert_iter( iterator pos, InputIterator first, InputIterator last )
	{
		InsertIterator( pos, first, last, typename is_pod<T>::type() );
	}

	iterator erase( iterator it )
	{
		FC_ASSERT(it >= begin() && it < end());
		fc::copy( it + 1, m_end, it );
		fc::destroy(--m_end);

		return it;
	}

	iterator erase( iterator first, iterator last )
	{
		FC_ASSERT(iterator_is_valid(first) && iterator_is_valid(last));
		FC_ASSERT(first <= last);

		T* ptr = fc::copy( last, m_end, first );
		fc::destroy_n( ptr, size_t(last - first) );
		m_end -= (last - first);

		return first;
	}

	iterator erase_unordered( iterator it )
	{
		FC_ASSERT(it >= begin() && it < end());
		*it = *(--m_end);
		fc::destroy( m_end );

		return it;
	}

	void erase_unordered_at( size_t pos ) { erase_unordered( m_begin + pos ); }
	void erase_at( size_t pos ) { erase( m_begin + pos ); }
	void erase_at( size_t pos, size_t n ) { erase( m_begin + pos, m_begin + pos + n ); }

	void push_back()
	{
		if( FC_LIKELY(m_end != m_capacity) )
			fc::construct(m_end++);
		else
		{
			grow();
			fc::construct(m_end++);
		}
	}

	void push_back( const T& value )
	{
		if( FC_LIKELY(m_end != m_capacity) )
			fc::construct(m_end++, value);
		else
		{
			grow();
			fc::construct(m_end++, value);
		}
	}

	T* push_back_uninitialized( size_t n = 1 )
	{
		if( FC_UNLIKELY(m_end + n > m_capacity) )
			grow(n);

		m_end += n;
		return m_end - n;
	}

	void pop_back()
	{
		FC_ASSERT(!empty());
		fc::destroy(--m_end);
	}

	void push_front( const T& value = T() ) { insert( m_begin, value ); }
	void pop_front() { erase(m_begin); }

	this_type& operator =( const this_type& x )
	{
		if( this != &x )
			assign_iter( x.begin(), x.end() );
		return *this;
	}

	template <class U>
	this_type& operator =( const vector<T, U>& x )
	{
		assign_iter( x.begin(), x.end() );
		return *this;
	}

	bool iterator_is_valid( const_iterator it ) const
	{
		return (it >= m_begin && it <= m_end);
	}

	void grow( size_t minimumGrowth = 1 )
	{
		const size_t newCapacity = get_new_capacity(minimumGrowth);
		const size_t newSize = size_t(m_end - m_begin);
		T* newBegin = allocate_copy( newCapacity, m_begin, m_end );

		fc::destroy_range(m_begin, m_end);
		deallocate();

		m_begin = newBegin;
		m_end = newBegin + newSize;
		m_capacity = newBegin + newCapacity;
	}

	size_t get_new_capacity( size_t minimumGrowth ) const
	{
		const size_t oldCapacity = size_t(m_capacity - m_begin);
		size_t newCapacity = oldCapacity ? (oldCapacity * 2) : FC_MIN_VECTOR_GROWTH;
		if( newCapacity < oldCapacity + minimumGrowth )
			newCapacity = oldCapacity + minimumGrowth;

		return newCapacity;
	}

protected:
	template <class InputIterator>
	inline void AssignDispatch( InputIterator first, InputIterator last, const false_type& )
	{
		AssignIterator( first, last, typename is_pod<T>::type() );
	}

	template <class Integral>
	inline void AssignDispatch( Integral n, Integral value, const true_type& )
	{
		AssignValues( (size_t)n, (T)value, typename is_pod<T>::type() );
	}

	template <class InputIterator>
	inline void InsertDispatch( iterator pos, InputIterator first, InputIterator last, const false_type& )
	{
		InsertIterator( pos, first, last, typename is_pod<InputIterator>::type() );
	}

	template <class Integral>
	inline void InsertDispatch( iterator pos, Integral n, Integral value, const true_type& )
	{
		InsertValues( pos, n, value, typename is_pod<T>::type() );
	}

	template <class InputIterator>
	inline void InitializeDispatch( InputIterator first, InputIterator last, const false_type& )
	{
		InitializeIterator( fc::distance(first, last), first, last );
	}

	template <class Integral>
	inline void InitializeDispatch( Integral n, Integral value, const true_type& )
	{
		InitializeValues( (size_t)n, value );
	}

	template <class ForwardIterator>
	void AssignIterator( ForwardIterator first, ForwardIterator last, true_type )
	{
		const size_t n = fc::distance(first, last);
		if( n > size_t(m_capacity - m_begin) )
		{
			deallocate();
			m_begin = allocate_copy( n, first, last );
			m_end = m_capacity = m_begin + n;
		}
		else
		{
			m_end = fc::copy( first, last, m_begin );
		}
	}

	template <class ForwardIterator>
	void AssignIterator( ForwardIterator first, ForwardIterator last, false_type )
	{
		const size_t n = fc::distance(first, last);
		if( n > capacity() )
		{
			fc::destroy_range(m_begin, m_end);
			deallocate();

			m_begin = allocate_copy( n, first, last );
			m_end = m_capacity = m_begin + n;
		}
		else
		if( n > size() )
		{
			ForwardIterator mid = first;
			fc::advance( mid, size() );
			m_end = fc::uninitialized_copy( mid, last, fc::copy(first, mid, m_begin) );
		}
		else
		{
			T* newEnd = fc::copy( first, last, m_begin );
			fc::destroy_n( newEnd, size_t(m_end - newEnd) );
			m_end = newEnd;
		}
	}

	void AssignValues( size_t n, const T& value, true_type )
	{
		if( n > capacity() )
		{
			deallocate();
			m_begin = allocate_fill( n, value );
			m_end = m_capacity = m_begin + n;
		}
		else
		{
			m_end = fc::fill_n( m_begin, n, value );
		}
	}

	void AssignValues( size_t n, const T& value, false_type )
	{
		if( n > capacity() )
		{
			fc::destroy_range(m_begin, m_end);
			deallocate();

			m_begin = allocate_fill( n, value );
			m_end = m_capacity = m_begin + n;
		}
		else
		if( n > size() )
		{
			fc::fill( m_begin, m_end, value );
			fc::uninitialized_fill( m_end, m_begin + n, value );
			m_end = m_begin + n;
		}
		else
		{
			fc::fill_n( m_begin, n, value );
			erase( m_begin + n, m_end );
		}
	}

	// this function is shared between all specializations of insert(..)
	// and would be called when a reallocation is needed to meet the new capacity
	// requirements.

	T* InsertReallocate( iterator pos, size_t n )
	{
		const size_t newCapacity = get_new_capacity(n);
		T* newBegin = allocate(newCapacity);

		T* newPos = fc::uninitialized_copy( m_begin, pos, newBegin );
		T* newEnd = fc::uninitialized_copy( pos, m_end, newPos + n );

		fc::destroy_range(m_begin, m_end);
		deallocate();

		m_begin = newBegin;
		m_end = newEnd;
		m_capacity = newBegin + newCapacity;

		return newPos;
	}

	iterator InsertValue( iterator pos, const T& value, true_type )
	{
		FC_ASSERT(iterator_is_valid(pos));

		if( FC_LIKELY(m_capacity != m_end) )
		{
			if( pos == m_end )
				*m_end++ = value;
			else
			{
				// value is simple pod-type, simply create a temporary object.
				const T temp = value;
				T* last = m_end;
				fc::copy_backward( pos, last, ++m_end );
				*pos = temp;
			}
		}
		else
		{
			pos = InsertReallocate( pos, size_t(1) );
			*pos = value;
		}

		return pos;
	}

	iterator InsertValue( iterator pos, const T& value, false_type )
	{
		FC_ASSERT(iterator_is_valid(pos));

		// optimize for common cases by assuming we are not full,
		// and that there is a possibility that we are inserting to end.
		// by doing this we can avoid many cases where a copy of the original
		// value must be constructed when its address is between [it, end).

		if( FC_UNLIKELY(m_capacity != m_end) )
		{
			if( pos == m_end )
				fc::construct( m_end++, value );
			else
			{
				// optimization for possibly large data types.
				const T* ptrVal = &value;
				if( (ptrVal >= pos) && (ptrVal < m_end) )
					++ptrVal;

				T* last = m_end - 1;
				fc::construct( m_end, *(last) );
				fc::copy_backward( pos, last, m_end++ );
				*pos = *ptrVal;
			}
		}
		else // reallocate
		{
			pos = InsertReallocate( pos, size_t(1) );
			fc::construct( pos, value );
		}

		return pos;
	}

	template <class ForwardIterator>
	void InsertIterator( iterator pos, ForwardIterator first, ForwardIterator last, true_type )
	{
		FC_ASSERT(iterator_is_valid(pos));

		const size_t n = fc::distance( first, last );
		if( FC_LIKELY(size_t(m_capacity - m_end) >= n) )
		{
			fc::copy_backward( pos, m_end, m_end + n );
			fc::copy( first, last, pos );
			m_end += n;
		}
		else
		{
			T* p = InsertReallocate( pos, n );
			fc::copy( first, last, p );
		}
	}

	template <class ForwardIterator>
	void InsertIterator( iterator pos, ForwardIterator first, ForwardIterator last, false_type )
	{
		FC_ASSERT(iterator_is_valid(pos));
		const size_t n = fc::distance( first, last );

		if( FC_UNLIKELY(size_t(m_capacity - m_end) < n) )
		{
			T* p = InsertReallocate( pos, n );
			fc::uninitialized_copy( first, last, p );
		}
		else
		if( pos == m_end )
		{
			fc::uninitialized_copy( first, last, m_end );
			m_end += n;
		}
		else
		{
			const size_t rpos = size_type(m_end - pos);
			if( n <= rpos )
			{
				T* diff = m_end - n;
				fc::uninitialized_copy( diff, m_end, m_end );
				fc::copy_backward( pos, diff, m_end );
				fc::copy( first, last, pos );
			}
			else
			{
				fc::uninitialized_copy( pos, m_end, m_end + n - rpos );

				ForwardIterator mid = first;
				fc::advance( mid, rpos );
				fc::copy( first, mid, pos );
				fc::uninitialized_copy( mid, last, m_end );
			}
			m_end += n;
		}
	}

	void InsertValues( iterator pos, size_t n, const T& value, true_type )
	{
		FC_ASSERT(iterator_is_valid(pos));

		const value_type temp = value;
		if( FC_LIKELY(size_t(m_capacity - m_end) >= n) )
		{
			fc::copy_backward( pos, m_end, m_end + n );
			fc::fill_n( pos, n, temp );
			m_end += n;
		}
		else
		{
			T* p = InsertReallocate( pos, n );
			fc::fill_n( p, n, temp );
		}
	}

	void InsertValues( iterator pos, size_t n, const T& value, false_type )
	{
		FC_ASSERT(iterator_is_valid(pos));
		iterator newEnd = m_end + n;

		if( m_capacity < newEnd )
		{
			T* p = InsertReallocate( pos, n );
			fc::uninitialized_fill_n( p, n, value );
		}
		else
		if( pos == m_end )
			fc::construct_n( m_end, n, value ), m_end = newEnd;
		else
		{
			const value_type tmp = value;
			const size_t rpos = size_type(m_end - pos);
			if( n <= rpos )
			{
				iterator diff = m_end - n;
				fc::uninitialized_copy( diff, m_end, m_end );
				fc::copy_backward( pos, diff, m_end );
				fc::fill_n( pos, n, tmp );
			}
			else
			{
				fc::uninitialized_copy_backward( pos, m_end, newEnd );
				fc::construct_n( m_end, n - rpos, tmp );
				fc::fill_n( pos, rpos, tmp );
			}

			m_end = newEnd;
		}
	}

	void InitializeValues( size_t n, const T& value )
	{
		m_begin = base_type::allocate_fill( n, value );
		m_end = m_capacity = m_begin + n;
	}

	template <class ForwardIterator>
	void InitializeIterator( size_t n, ForwardIterator first, ForwardIterator last )
	{
		m_begin = base_type::allocate_copy( n, first, last );
		m_end = m_capacity = m_begin + n;
	}

};



// global vector operators

template <class T, class A1, class A2> inline
	void swap( const vector<T, A1>& a, const vector<T, A2>& b )
	{
		a.swap(b);
	}

template <class T, class A1, class A2> inline
	bool operator ==( const vector<T, A1>& a, const vector<T, A2>& b )
	{
		return( a.size() == b.size() && fc::equal(a.begin(), a.end(), b.begin()) );
	}

template <class T, class A1, class A2> inline
	bool operator !=( const vector<T, A1>& a, const vector<T, A2>& b )
	{
		return !(a == b);
	}

template <class T, class A1, class A2> inline
	bool operator <( const vector<T, A1>& a, const vector<T, A2>& b )
	{
		return lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
	}

template <class T, class A1, class A2> inline
	bool operator >( const vector<T, A1>& a, const vector<T, A2>& b )
	{
		return b < a;
	}

template <class T, class A1, class A2> inline
	bool operator <=( const vector<T, A1>& a, const vector<T, A2>& b )
	{
		return !(b < a);
	}

template <class T, class A1, class A2> inline
	bool operator >=( const vector<T, A1>& a, const vector<T, A2>& b )
	{
		return !(a < b);
	}



FC_NAMESPACE_END
